package com.just.fun.arithmetic;

import java.util.Arrays;

/**
 * 约瑟夫环
 * 数三退1问题
 * 500个小孩手拉手围成一圈，
 * 从第一个小孩开始数数，按照1、2、3、1、2、3循环不断的数，数到3的小孩退出圈，其他小孩接着数，直到剩下一个小孩，问这个小孩的排在什么位置？
 */
public class Joseph {
    public static void main(String[] args) {
        int n = 3;
        System.out.println("总小孩数：" + n);
        System.out.println("幸运儿：" + joseph1(n));
    }

    public static int joseph1(int n) {
        //定义一个布尔数组，true还在，false表示踢出去
        boolean[] people = new boolean[n];
        //初始化数据，两种方法
        /*for(int i=0;i<people.length;i++){
            people[i]=true;
        }*/
        Arrays.fill(people, true);

        int leftCount = people.length;// 剩下的人数，初值为500

        int countNum = 0;// 几个人一轮

        int index = 0;//数到第几个人

        while (leftCount > 1) {//只要剩余人数大于1，就继续数

            if (people[index]) {// 若数到第index个人，此人没有退出，就继续数

                countNum++;

                if (countNum == 3) {//数到3，此小孩出圈

                    countNum = 0;

                    people[index] = false;

                    leftCount--;

                }

            }

            index++;


            if (index == people.length) {

                index = 0;

            }

        }

        for (int i = 0; i < people.length; i++) {

            if (people[i]) {

                return i+1;

            }

        }
        return 0;

    }
}
